#include "global.h"
#include <cassert>
#include <cstdio>
#include <cmath>

static double dp[1<<MAX_TAG_NUM][MAX_TAG_NUM],val[MAX_TAG_NUM][MAX_TAG_NUM];
static int pre[1<<MAX_TAG_NUM][MAX_TAG_NUM],sum_read[MAX_TIME_SLICING];
int vtag[MAX_TAG_NUM],tagpos[MAX_TAG_NUM];
void Dp_calc()
{
	/*
		使用状态压缩dp来对tag在磁盘上的顺序进行排序。通过综合考虑各个tag的读取频率和占磁盘的空间大小计算出tag两两的权值，
	使得磁盘上的相邻tag的读取频率越相似，权值越高；且占用空间大小差异越大，权值越高。dp[s][i]表示当前已选tag为s中二进制位
	为1的对应tag，i表示当前状态最后一个tag是哪个。pre[s][i]表示当前状态的最优前置状态。
	*/
	static int occupy[MAX_TAG_NUM][MAX_TIME_SLICING];
	for(int i=1;i<=M;i++)
		for(int j=1;j<=M;j++) val[i][j]=0;

	const int tlen=100,step=100;
	const double read_rate=0.1,occ_rate=4.0;
	for(int k=tlen;k<=T+EXTRA_TIME;k+=step)
	{
		for(int i=1;i<=M;i++)
		{
			occupy[i][k]=occupy[i][k-1]+(get_num_write(i,k-tlen+1,k)-get_num_delete(i,k-tlen+1,k))*3;
			sum_read[k]+=get_num_read(i,k-tlen+1,k);
		}
	}

	for(int k=tlen;k<=T+EXTRA_TIME;k+=step)
	{
		for(int i=1;i<=M;i++)
			for(int j=1;j<=M;j++) if(i!=j)
			{
				if (sum_read[k]!=0) val[i][j]+=read_rate*get_num_read(i,k-tlen+1,k)*get_num_read(j,k-tlen+1,k)/sum_read[k];
				val[i][j]-=occ_rate*occupy[i][k]*occupy[j][k]/(N*V);
				// val[i][j]+=fre_write[i][k]*fre_de[j][k]+fre_write[j][k]*fre_de[i][k];
			}
	}
		

	for(int s=0;s<(1<<M);s++)
		for(int i=1;i<=M;i++) dp[s][i]=-1e40;

	for(int i=1;i<=M;i++) dp[(1<<(i-1))][i]= 0,pre[(1<<(i-1))][i]=i;
	for(int s=1;s<(1<<M);s++)
	{
		int min_i=0,Len=0;
		for(int i=1;i<=M;i++) Len+=((s>>(i-1))&1);
		for(int i=1;i<=M;i++)
			if((s>>(i-1))&1) {min_i=i;break;}
		for(int i=min_i;i<=M;i++) if(s&(1<<(i-1)))
			for(int j=min_i+1;j<=M;j++) if(!(s&(1<<(j-1))))
				if(dp[s|(1<<(j-1))][j]<dp[s][i]+val[i][j])
					dp[s|(1<<(j-1))][j]=dp[s][i]+val[i][j],pre[s|(1<<(j-1))][j]=i;
	}
}
void Sort()
{
	/*
		使用状压DP对tag在磁盘上的顺序进行排序
	*/
	Dp_calc();

	int listcnt=0;
	int min_i=1,maxs=65535;
	int id=0;double maxdp=-1e20;
	for(int i=1;i<=M;i++)
		if(maxdp<dp[maxs][i]+val[i][min_i]) maxdp=dp[maxs][i]+val[i][min_i],id=i;
	vtag[++listcnt]=id;
	for(int s1=maxs;id!=min_i;)
	{
		vtag[++listcnt]=pre[s1][id];
		s1^=(1<<(id-1));id=vtag[listcnt];
	}
	assert(listcnt==M);
	for(int i=1;i<=M;i++) tagpos[vtag[i]]=i;
	for(int i=1;object[i].size;i++)
		object[i].tag=tagpos[object[i].tag];
	#ifdef STATISITIC_ON
	FILE *file=fopen("tag.txt","w");
	for(int i=1;object[i].size;i++){
		fprintf(file,"%d ",object[i].tag);
	}
	fclose(file);
	file=fopen("read.txt","w");
	for(int tag=1;tag<=M;tag++){
		for(int i=1;i<=T+EXTRA_TIME;i++)
			fprintf(file,"%d ",get_num_read(tag,i));
		fprintf(file,"\n");
	}
	fclose(file);
	file=fopen("write.txt","w");
	for(int tag=1;tag<=M;tag++){
		for(int i=1;i<=T+EXTRA_TIME;i++)
			fprintf(file,"%d ",get_num_write(tag,i));
		fprintf(file,"\n");
	}
	fclose(file);
	file=fopen("delete.txt","w");
	for(int tag=1;tag<=M;tag++){
		for(int i=1;i<=T+EXTRA_TIME;i++)
			fprintf(file,"%d ",get_num_delete(tag,i));
		fprintf(file,"\n");
	}
	fclose(file);
	#endif
	for(int tag=1;tag<=M;tag++)
		fprintf(stderr,"%d ",vtag[tag]);
	fprintf(stderr,"\n");
	for(int tag=1;tag<=M;tag++)
		fprintf(stderr,"%d ",tagpos[tag]);
	fprintf(stderr,"\n");
	return;
}